package 二分算法;


/**
 * 在排序数组中查找第一个和最后一个位置
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
 */
public class likou34 {

    // 暴力枚举O(n) 二分是O(logN)
    public int[] searchRange(int[] nums, int target) {
        // 查找区间的左端点 <t 和 >= t
        // todo 特例
        if(nums == null || nums.length <= 0) return new int[]{-1, -1};

        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2; // 左端点没有 + 1
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        int[] ret = new int[2];
        ret[0] = left;

        // 查找区间的右端点, <=T 和 >t
        // left 可以不用重置(因为答案在 left的右手边 或者是 >= left的地方). right 得重置
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        ret[1] = right;
        // todo 不一定有答案
        if(nums[left] != target) return new int[]{-1, -1};
        return ret;
    }


}
